package com.yangzhe.algorithm.c037;

// 普通二叉树上寻找两个节点的最近公共祖先
// 测试链接 : https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/
public class Code01_LowestCommonAncestor_LeetCode {

    // 不提交这个类
    public static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;
    }

    /**
     * 题目为经典LCA
     * 思路：利用递归，分别查找root.left和root.right左右子树
     * 1. 如果root.left有，root.right没有，则代表p和q都在左子树，那这个root节点就是LCA。反之亦然
     * 2. 如果root.left有，root.right也有，则代表当前root节点就是LCA
     * 3. 如果root.left没有，root.right也没有，则代表当前root的子树没有LCA
     * <p>
     * 时间复杂度：O(N)，其中 N 是树中节点的总数，最坏情况下需要访问所有节点。
     * 空间复杂度：O(H)，H 是树的高度，主要是递归调用栈的空间。最坏情况下（链状树）为 O(N)，平衡树为 O(log N)。
     *
     * @param root
     * @param p
     * @param q
     * @return
     */
    public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // base case：当前分支已经到底了，或者找到了q或者q
        if (root == null || root == p || root == q) {
            return root;
        }

        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);

        // 如果左边有p或q，右边也有p或q，则代表当前节点就是LCA
        if (left != null && right != null) {
            return root;
        }

        // LCA不在当前子树
        if (left == null && right == null) {
            return null;
        }

        // 当前分支找到的p或q继续向上级返回
        return left != null ? left : right;
    }

}
